今天來實作二元樹～

首先來定義一下資料結構

type Node struct {
	Left  *Node
	Right *Node
	Val   int
}

type BinarySearchTree struct {
	root *Node
}

我們需要來insert新的節點，還記得比較小的要放在左邊，比較大的放在右邊嗎？
insert的時候就是要一個一個node做判斷，去找到適合放的位置，如果插入值比目前node的值小，就看它左邊的節點是不是空的，如果是就可以放，否則再往左邊的node繼續找。
如上圖，假設我們現在要insert一個5的值，那走訪的順序為: 10->3->4 放在右邊節點

新增:

func (t *BinarySearchTree) Insert(val int) {
	newNode := &Node{
		Val: val,
	}

	if t.root == nil {
		t.root = newNode
		return
	}

	node := t.root
	for {
		if val == node.Val {
			return
		}

		if val < node.Val {
			// 左邊剛好是空的
			if node.Left == nil {
				node.Left = newNode
				return
			}

			// 繼續往左找
			node = node.Left
		} else {
			// 右邊剛好是空的
			if node.Right == nil {
				node.Right = newNode
				return
			}

			// 繼續往右找
			node = node.Right
		}
	}
}

搜尋:

func (t *BinarySearchTree) Find(val int) bool {
	node := t.root

	for {
		if node == nil {
			return false
		}

		if node.Val == val {
			return true
		}

		if val < node.Val {
			node = node.Left
		} else {
			node = node.Right
		}
	}
}

今天先到這邊，明天再繼續會講樹～